#include <iostream>
#include <vector>
// 基于暴力搜索+回溯的解法
// 每次选择后都有(n-1)种选择, 时间复杂度为 O(n!)
void backtrace(const std::vector<int> &steps, int n, int &nums) {
  if (n == 0) {
    nums++;
  }
  for (int step : steps) {
    if (n - step >= 0) {
      backtrace(steps, n - step, nums);
    }
    if (n - step < 0) {
      return;
    }
  }
}
int climbingStairsBacktrack(int n) {
  std::vector<int> steps{1, 2};
  int nums{0};
  backtrace(steps, n, nums);
  return nums;
}

// 基于递归的解法
// f(n) = f(n-1)+f(n-2)
// 时间复杂度 O(2^n)
int dfs(int n) {
  if (n == 1 || n == 2) {
    return n;
  }
  return dfs(n - 1) + dfs(n - 2);
}

int climbingStairsBacktrack_dfs(int n) { return dfs(n); }

// 时间复杂度 O(n)
int dfs_mem(int n, std::vector<int> &mem) {
  // 该值已经计算过 剪枝
  if (mem[n] != -1) {
    return mem[n];
  }
  int count = dfs(n - 1) + dfs(n - 2);
  mem[n] = count;
  return count;
}
// 记忆化搜索解法 从顶至底 将大问题逐步分解为小问题
int climbingStairsBacktrack_dfs_mem(int n) {
  std::vector<int> mem(n + 1, -1);
  mem[1] = 1;
  mem[2] = 2;
  return dfs_mem(n, mem);
}
// 动态规划解法 从小问题开始解决，直到问题规模达到求解的问题规模
// 时间复杂度O(n)
int climbingStairsBacktrack_dp(int n) {
  std::vector<int> dp(n + 1, -1);
  dp[1] = 1;
  dp[2] = 2;
  for (int i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

int climbingStairsBacktrack_dp_scope(int n) {
  std::vector<int> dp(n + 1, -1);
  int a = 1;
  int b = 2;
  int count = 0;
  for (int i = 3; i <= n; i++) {
    int t = b;
    b = a + b;
    a = t;
  }
  return b;
}

int main() {
  int n = 3;
  // int nums = climbingStairsBacktrack(n);
  // int nums = climbingStairsBacktrack_dfs(n);
  // int nums = climbingStairsBacktrack_dfs_mem(n);
  // int nums = climbingStairsBacktrack_dp(n);
  int nums = climbingStairsBacktrack_dp_scope(n);
  std::cout << nums << std::endl;
}